The present invention relates to constraint programming, and more particularly relates to a system and method for automatically solving constraint satisfaction problems that provides explanations as to why specific constraints were chosen, and why they do not provide solutions, as the case may be.
Constraint programming may be characterized broadly as declarative programming, a technique by which a program essentially describes what is to be computed (processed). Declarative program is distinguishable with respect to imperative programming, by which a program describes how an output must be computed. Constraint programs are more specifically referred to as constraint satisfaction problems, or CSPs. CSPs operate upon a set of variables, wherein each variable is “constrained” to a set of values. During operation, each CSP constraint may be applied to a subset of the variables within the set of variables, by which the CSP application program restricts the values that the variables may assume. Preparing a CSP to represent a combinatorial problem that occurs in practice is referred to as modeling, where the purpose of constraint solving is to generate solutions to CSP model.
Many problems from different domains, such as combinatorial optimization problems and test generation problems are modeled as CSPs. An example of such a model for a combinatorial optimization problem is described in a paper by Eyal Bin, at al., entitled: Using Constraint Satisfaction Formulations And Solution Techniques For Random Test Program Generation, IBM System Journal, Special Issue on AI, August 2002.
Another common approach to solving CSPs includes the use of a “Maintaining Arc Consistency”, or MAC algorithm. MAC algorithms, and constraint problem solving based thereon is described in detail in a paper by A. K. Mackworth, entitled: Consistency In Networks Of Relations, Artificial Intelligence, 8:99-118, 1977. In MAC operation, a constraint is specified by a propagator. Propagators are procedures that filter from the constraint variables' domains values that cannot participate in a solution. An execution of MAC algorithm consists of repeated invocation of constraint propagators, alternating with non-deterministic choices, or assignment of a value or values to a variable.
Often, given a solution to a CSP problem, a user needs to have some understanding as to why specific values or constraints were chosen, or why other values were removed by the constraint propagators. For that matter, where the CSP problem is determined to be unsatisfiable, the user should understand why. The ability to explain the specific values (or lack of them) in a solution is pre-requisite for successful CSP modeling. Successful CSP modeling, for example, would support a task of successfully debugging an imperative program, which ability and successful debugging is a basic need in any successful software development.
For that matter, known CSP debugging is normally performed off-line, and is therefore sometimes referred to by the skilled artisan as “post-mortem.” During a MAC execution, a trace of events (“trace”) is generated and analyzed afterwards. i.e., post mortem, upon completion of the process. The trace gives rise to a CSP execution graph. A CSP execution graph highlights two kinds of nodes: 1) variable domains and 2) solver events that transform variable domains. There is a directed edge from a variable domain to solver event. The directed edge denotes input of a solver event, and the directed edge from the solver event to an output. FIG. 1 herein is an exemplary embodiment of a CSP model. In this figure x and y are two integer variables with an initial domain of [1,10] and [3,15] respectively. Each oval node “x>y” is a propagation event and the oval node “instantiate x” is an instantiation event.
Finding explanations for the given solution for a CSP execution graph typically requires traversing the graph backwards. Such explanations correspond to a sub-graph of the CSP execution graph, which when viewed as set of variable reductions and propagations, supplies an evidence based reasoning supporting why a specific variable was attributed to or assigned a specific value. There may be numerous explanations for an observed effect, such that a significant shortcoming of the conventional process is that the debugging process typically focuses on a single explanation. While the whole of the CSP execution graph inherently provides what may be described as a global explanation, practical investigation and specific user needs tend to focus on a user's particular interest in a minimal sub-graph (or explanation). The term sub-graph as used herein is meant represent a minimal explanation for an effect if removing an event from a sub-graph doesn't imply or reflect that the event is the basis for the effect, or that the event is not readily inferable from the sub-graph.
Finding a single minimal explanation requires tracking several paths in the execution graph. The task of tracking the several paths to identify a single minimal explanation, when performed manually, is tedious and labor-intensive. Even discovering immediate causes of a variable reduction by analyzing a single constraint invocation is not trivial. An existing constraints programming environment with explanation support, or “Palm,” is described by N. Jussien and V. Barichard, in their paper: The PaLM System: Explanation-Based Constraint Programming, Proceedings of TRICS: Techniques For Implementing Constraint Programming Systems. Proceedings of TRICS is a post-conference workshop of CP 2000. “Palm” explicitly requires augmenting the constraint propagators for producing explanations. Similar ideas to those used in the “Palm” system for producing explanations are discussed in a paper by R. J. Wallace, E. C. Freuder, in their paper: Explanations For Whom? In Proc.; CP 2001.
What would be desirable in the art of identifying explanations for given solutions for CSP execution graphs is a system and method that processes and generates explanations in at least two particular cases. The first of the two cases arises where the CSP solver returns no result for the selected variables, i.e., the case of a CSP failure. The second of the two cases arises where the CSP solver returns a specific domain for one of the variables. Moreover, the method preferably would operate offline, or post mortem, and would focus or operate based on a trace generated by the CSP solver.